package main

import (
	"fmt"
)

func main(){
	arr := []int{3, 6, 1, 4, 2, 8}
	fmt.Println(arr)
	quickSort(arr, 0, len(arr)-1)
	fmt.Println(arr)
}

/**
递归
 */
func quickSort(arr []int, left, right int) {
	if left >= right {
		return
	}
	index := partition(arr,left,right)
	quickSort(arr, left, index - 1)
	quickSort(arr, index + 1, right)
}

/**
https://blog.csdn.net/pengzonglu7292/article/details/84938910
 简单的说就是
	先从有往左找到第一个比基准值大的值，从左往右找到第一个比基准值小的值，对调位置
	然后继续上述步骤，直到left>=right
	最后基准值和arr[right]对调
 */
func partition(arr []int, left, right int) int {
	baseNum := arr[left]
	for left < right{

		//从右往左，如果找到比基准值大的，继续往左找
		for arr[right] >= baseNum && right > left {
			right--
		}
		///从右往左，找到第一个比基准值大的值，赋值给左测的索引对应的值
		arr[left] = arr[right]
		fmt.Println(arr)

		//从左往右，找到第一个比基准值小的值，赋值给右侧当前索引值
		for arr[left] <=baseNum && right > left {
			left++
		}
		arr[right] = arr[left]
		fmt.Println(arr)
	}
	//当前右侧索引的值替换成基准值
	arr[right] = baseNum
	fmt.Println(arr)
	return right
}